package com.gxc.array;

/**
 * 给定两个一维int数组A和B.
 * 其中:
 * A是长度为m、元素从小到大排好序的有序数组。
 * B是长度为n、元素从小到大排好序的有序数组。
 * 希望从A和B数组中，找出最大的k个数字，要求:使用尽量少的比较次数。
 *
 * 解法:
 * 1）两个数组从最大的开始比较，不满足使用尽量少的比较次数
 * 2）a情形---A数组的最小值比B数组的最大值都大，最大的k个数字先取A数组，再取B数组
 *    b情形---B数组的最小值比A数组的最大值都大，最大的k个数字先取B数组，再取A数组
 *    c情形---先从A和B数组中各取出K个大数字（如数量不够，取全部数组），
 *    用二分法比较，大数组的后半区间肯定处于最大的k个数字，
 *    然后递归二分比较
 * 3）上中位数（算法原理）
 *      比较中位数大小，大的数字后面的数都抛弃，小的数字前面的数都抛弃
 *      题目转为求第K个大的数
 *
 */
public class KNumber {

    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 2};
        int[] arr2 = new int[]{3, 4, 5};

        System.out.println(process(arr1, arr2, 2));

        System.out.println("---------");

        //System.out.println(upMedian(arr1, 0, 2, arr2, 0, 3));
        //System.out.println(upMedian2(arr1, 0, 2, arr2, 0, 3));
    }

    public static int process(int[] arr1, int[] arr2, int k) {
        if (arr1 == null || arr2 == null) return 0;

        if (k > arr1.length + arr2.length) return 0;

        int[] longArr = arr1.length>arr2.length?arr1:arr2;
        int[] shortArr = arr1.length>arr2.length?arr2:arr1;

        int l = longArr.length;
        int s = shortArr.length;

        //如果K小于最短的数组长度
        // k = 4
        //[1,2,3,4,5,6]
        //[1,2,3,4,5,6,7,8,9]
        if (k < s) {
            return upMedian(shortArr, shortArr.length-k, shortArr.length-1, longArr, longArr.length-k, longArr.length-1);
        } else if (k>=s && k<=l) {
            // k = 8
            //[1,2,3,4,5,6]
            //[1,2,3,4,5,6,7,8,9]
            if (longArr[l+s-k-1]<shortArr[0]) {
                return longArr[l+s-k-1];
            }
            return upMedian(shortArr, 0, shortArr.length-1, longArr, longArr.length-k, longArr.length-k+s-1);
        } else if (k>l){
            // k = 11
            //[1,2,3,4,5,6]
            //[1,2,3,4,5,6,7,8,9]
            if (shortArr[s+l-k-1]<=longArr[0]) {
                return shortArr[s+l-k-1];
            }
            if (longArr[l+s-k-1]<=shortArr[0]) {
                return longArr[s+l-k-1];
            }
            return upMedian(shortArr, 0, l+s-k-1, longArr, 0, l+s-k-1);
        }
        return 0;
    }

    /**
     * 获取数组的上中位数的位置
     * @param arr1
     * @param s1
     * @param e1
     * @param arr2
     * @param s2
     * @param e2
     * @return
     */
    public static int upMedian(int[] arr1, int s1, int e1, int[] arr2, int s2, int e2) {
        int num = e1 - s1;
        if (num ==0) {
            return arr1[s1]>arr2[s2]?arr2[s2]:arr1[s1];
        }

        //上中位数
        int upMedian = s1 + (e1-s1)/2;
        int upMedian2 = s2 + (e2-s2)/2;
        /**
         * 数组为奇数   0-4   0,1,2,3,4
         */
        if (num%2 == 0 ) {
            if (arr1[upMedian] == arr2[upMedian2]) return upMedian;
            else if (arr1[upMedian] < arr2[upMedian2]) {
                return upMedian(arr1, upMedian, e1, arr2, s2, upMedian2);
            } else {
                return upMedian(arr1, s1, upMedian, arr2, upMedian2, e2);
            }
        } else {
            /**
             * 数组为偶数
             */
            if (arr1[upMedian] == arr2[upMedian2]) return upMedian;
            else if (arr1[upMedian] < arr2[upMedian2]) {
                return upMedian(arr1, upMedian+1, e1, arr2, s2, upMedian2);
            } else {
                return upMedian(arr1, s1, upMedian, arr2, upMedian2+1, e2);
            }
        }
    }

    /**
     * 循环查找上中位数
     * @param arr1
     * @param s1
     * @param e1
     * @param arr2
     * @param s2
     * @param e2
     * @return
     */
    public static int upMedian2(int[] arr1, int s1, int e1, int[] arr2, int s2, int e2) {

        int upMedian = 0;
        int upMedian2 = 0;
        int offset = 0;
        while (s1<e1) {
            upMedian = s1 + (e1-s1)/2;
            upMedian2 = s2 + (e2-s2)/2;
            //区分奇数和偶数
            offset = ((e1 -s1) & 1);
            if (arr1[upMedian] == arr2[upMedian2]) return arr1[upMedian];
            else if (arr1[upMedian] < arr2[upMedian2]) {
                s1 = upMedian + offset;
                e2 = upMedian2;
            } else {
                e1 = upMedian;
                s2 = upMedian2 + offset;
            }
        }
        return Math.min(arr1[s1], arr2[s2]);
    }

}
